package com.currentbp.Interesting.likou.complete;

import org.junit.Test;

/**
 * @author baopan
 * @createTime 2024/3/17 22:53
 */
public class T1524numOfSubarrays {

    /*
    给你一个整数数组 arr 。请你返回和为 奇数 的子数组数目。
由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。
示例 1：
输入：arr = [1,3,5]
输出：4
解释：所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]] 。
所有子数组的和为 [1,4,9,3,8,5].
奇数和包括 [1,9,3,5] ，所以答案为 4 。
示例 2 ：
输入：arr = [2,4,6]
输出：0
解释：所有子数组为 [[2],[2,4],[2,4,6],[4],[4,6],[6]] 。
所有子数组和为 [2,6,12,4,10,6] 。
所有子数组和都是偶数，所以答案为 0 。
示例 3：
输入：arr = [1,2,3,4,5,6,7]
输出：16
示例 4：
输入：arr = [100,100,99,99]
输出：4
示例 5
输入：arr = [7]
输出：1
提示：
1 <= arr.length <= 10^5
1 <= arr[i] <= 100
     */

    /*
    解题思路：
    1、只需要统计奇数数量
    2、每个数字可以用0 or 1表示，因为只需要最后的结果是奇数的
    3、弄一个二维数组，a[i][j]表示从第i到第j的奇偶性
    4、默认值为0，表示偶，只需要得到奇就行
     */
    @Test
    public void t1() {
        System.out.println(numOfSubarrays(new int[]{1, 3, 5}));
        System.out.println(numOfSubarrays(new int[]{2, 4, 6}));
        System.out.println(numOfSubarrays(new int[]{1, 2, 3, 4, 5, 6, 7}));
        System.out.println(numOfSubarrays(new int[]{100, 100, 99, 99}));
        System.out.println(numOfSubarrays(new int[]{7}));
    }

    /**
     * 可以说是计算完成，但是内存超过了，我自己无法再优化了
     */
    public int numOfSubarrays(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int[][] flags = new int[arr.length][arr.length];

        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                if (i == j) {//第一个
                    flags[i][j] = arr[i] % 2 == 0 ? 0 : 1;
                    result += flags[i][j];
                    continue;
                }
                flags[i][j] = (flags[i][j - 1] + arr[j]) % 2 == 0 ? 0 : 1;
                result += flags[i][j];
            }
        }
        return result;
    }

}
